/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  // 剪枝的前提是排序
  nums = nums.sort((a, b) => { return a - b; });

  // 定义三个数组
  // 1.res 用于存放结果集
  // 2.stack 用于回溯存放的数值
  // 3.used 用于判断某个数值是否已经被存放过了
  let res = [],
    stack = [],
    used = new Array(nums.length).fill(false);
  // dfs 关键函数,回溯重点
  function dfs(depth) {
    // 如果说深度和nums的长度一样了
    // 说明当前的stack中的数值已经存完了nums里面的各个数值
    // 因此只需要装入即可
    if (depth == nums.length) {
      res.push([...stack]);
      return;
    }
    // 开始遍历
    for (let i = 0; i < nums.length; i++) {
      // 1.如果这个数已经被stack装入过，则跳过
      // 2.如果没有被stack装入过，则装入，同时设置used[i]为true
      if (!used[i]) {
        // 如果上一个数与这个数相等，并且上一个数已经加入到了stack当中，就选择跳过
        // if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
        //   continue;
        // }
        // 如果下一个数与这个数相等，并且下一个数已经加入到了stack当中，就选择跳过
        if(i < nums.length && nums[i] == nums[i + 1] && !used[i + 1]) {
          continue;
        }
        stack.push(nums[i]);
        used[i] = true;
        // 继续下一层级的查找
        dfs(depth + 1);
        // 回溯，将以前的值变回原样
        used[i] = false;
        stack.splice(stack.length - 1, 1);
      }
    }
  }
  dfs(0);
  return res;
};
let nums = [1, 1, 2];
console.log(permuteUnique(nums));
nums = [1, 2, 3];
console.log(permuteUnique(nums));
